package com.since.data_structure.linkedlist;

import java.util.LinkedList;

/**
 * Created by Sincerity on 2020/5/8.
 * 描述：约瑟夫环问题
 * 0,1,,n-1这n个数字排成一个圆圈，从数字0开始，
 * 每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
 */
class Joseph {
    /**
     * 链表
     *
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining4(int n, int m) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        if (n == 0 || m == 0) {
            return -1;
        }
        for (int i = 0; i < n; i++) {
            linkedList.add(i);
        }
        int removeIndex = 0;
        while (linkedList.size() != 1) {
            removeIndex = (removeIndex + m - 1) % linkedList.size();
            linkedList.remove(removeIndex);
        }
        return linkedList.get(0);
    }

    /**
     * 环形链表实现
     *
     * @param n 总条目数
     * @param m 从第几个开始删除
     * @return 返回最后剩下的数字
     */
    public Entry lastRemaining3(int n, int m) {
        Entry head = null;
        Entry tail = null;
        for (int i = 1; i < n; i++) {
            Entry newEntry = new Entry(i);
            if (i == 1) {
                head = newEntry;
                tail = head;
            } else {
                tail.next = newEntry;
                tail = newEntry;
            }

        }
        tail.next = head;
        Entry p = head;
        while (p.next != head) {
            p = p.next;
        }
        Entry pre = null;
        Entry t = null;
        p = head;
        int flag = 1;
        while (p.next != p) {
            if (flag == 3) {
                t = p.next;
                pre.next = t;
                p = t;
                flag = 1;
            } else {
                pre = p;
                p = p.next;
                flag++;
            }
        }
        return p;
    }

    /**
     * 数学公式
     *
     * @param n 总条数
     * @param m 从第几个开始删除
     * @return 返回最后剩下的数字
     */
    public int lastRemaining(int n, int m) {
        return n == 1 ? 0 : (lastRemaining(n - 1, m) + m) % n;
    }

    /**
     * 数学公式
     *
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining2(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int last = 0;
        for (int i = 2; i <= n; i++) {
            last = (last + m) % i;
        }
        return last;
    }

    static class Entry {
        Entry head;
        Entry next;
        int no;

        public Entry(int no) {
            this.no = no;
        }

        @Override
        public String toString() {
            return "Entry{" +
                    "no=" + no +
                    '}';
        }
    }
}
